<!DOCTYPE html>
<html lang="en-US">
  <head>
    <meta charset="utf-8">
    <meta name="viewport" content="width=device-width,initial-scale=1">
    <title>DP动态规划 | whoway</title>
    <meta name="description" content="Personal Blog Website">
    <link rel="icon" href="/images/photo.jpg">
  <link rel="manifest" href="/images/photo.jpg">
  <link rel="apple-touch-icon" href="/images/photo.jpg">
  <meta http-quiv="pragma" cotent="no-cache">
  <meta http-quiv="pragma" cotent="no-cache,must-revalidate">
  <meta http-quiv="expires" cotent="0">
    
    <link rel="preload" href="/assets/css/0.styles.0dbae9ec.css" as="style"><link rel="preload" href="/assets/js/app.c70e21ad.js" as="script"><link rel="preload" href="/assets/js/63.6f8a4742.js" as="script"><link rel="prefetch" href="/assets/js/10.15222a53.js"><link rel="prefetch" href="/assets/js/100.7e0e5a86.js"><link rel="prefetch" href="/assets/js/101.efd59f25.js"><link rel="prefetch" href="/assets/js/102.dfbdc06c.js"><link rel="prefetch" href="/assets/js/103.d3ab2109.js"><link rel="prefetch" href="/assets/js/104.117957ef.js"><link rel="prefetch" href="/assets/js/105.046e8ff3.js"><link rel="prefetch" href="/assets/js/106.aebdc17d.js"><link rel="prefetch" href="/assets/js/107.248733c2.js"><link rel="prefetch" href="/assets/js/108.a2fecadc.js"><link rel="prefetch" href="/assets/js/109.35196857.js"><link rel="prefetch" href="/assets/js/11.770642f2.js"><link rel="prefetch" href="/assets/js/110.cf3d973c.js"><link rel="prefetch" href="/assets/js/111.f985889a.js"><link rel="prefetch" href="/assets/js/112.ad614f41.js"><link rel="prefetch" href="/assets/js/113.f666653c.js"><link rel="prefetch" href="/assets/js/114.c6c3f384.js"><link rel="prefetch" href="/assets/js/115.e51d3c2f.js"><link rel="prefetch" href="/assets/js/116.4f4b39f5.js"><link rel="prefetch" href="/assets/js/117.99352e11.js"><link rel="prefetch" href="/assets/js/118.c6ae6572.js"><link rel="prefetch" href="/assets/js/119.4ccbe778.js"><link rel="prefetch" href="/assets/js/12.042a92ff.js"><link rel="prefetch" href="/assets/js/120.edda1c4f.js"><link rel="prefetch" href="/assets/js/121.30a638ed.js"><link rel="prefetch" href="/assets/js/122.6efcefb1.js"><link rel="prefetch" href="/assets/js/123.91e6665b.js"><link rel="prefetch" href="/assets/js/124.f27e3d7e.js"><link rel="prefetch" href="/assets/js/125.c75712d5.js"><link rel="prefetch" href="/assets/js/126.ed756cce.js"><link rel="prefetch" href="/assets/js/127.2f06c74c.js"><link rel="prefetch" href="/assets/js/128.d5f6f30e.js"><link rel="prefetch" href="/assets/js/129.508b7eed.js"><link rel="prefetch" href="/assets/js/13.b5280c37.js"><link rel="prefetch" href="/assets/js/130.dc05f9aa.js"><link rel="prefetch" href="/assets/js/131.e0ba69b1.js"><link rel="prefetch" href="/assets/js/132.d79bcaa4.js"><link rel="prefetch" href="/assets/js/133.34acc01a.js"><link rel="prefetch" href="/assets/js/134.dabf64d5.js"><link rel="prefetch" href="/assets/js/135.ad90c915.js"><link rel="prefetch" href="/assets/js/136.dbb0074f.js"><link rel="prefetch" href="/assets/js/137.284ad365.js"><link rel="prefetch" href="/assets/js/138.a4b6856f.js"><link rel="prefetch" href="/assets/js/139.c9c1e20f.js"><link rel="prefetch" href="/assets/js/14.df02ba38.js"><link rel="prefetch" href="/assets/js/140.8b0a9269.js"><link rel="prefetch" href="/assets/js/141.9c7759c5.js"><link rel="prefetch" href="/assets/js/142.a4201a82.js"><link rel="prefetch" href="/assets/js/143.d7da6e8c.js"><link rel="prefetch" href="/assets/js/144.5e48e65d.js"><link rel="prefetch" href="/assets/js/145.a0e2633c.js"><link rel="prefetch" href="/assets/js/146.3c775f9b.js"><link rel="prefetch" href="/assets/js/147.22add89a.js"><link rel="prefetch" href="/assets/js/148.cfde1009.js"><link rel="prefetch" href="/assets/js/149.ffc835b5.js"><link rel="prefetch" href="/assets/js/15.fbdfc4ee.js"><link rel="prefetch" href="/assets/js/150.406c4b20.js"><link rel="prefetch" href="/assets/js/151.b2040eea.js"><link rel="prefetch" href="/assets/js/152.7bc65661.js"><link rel="prefetch" href="/assets/js/153.1d7c65e3.js"><link rel="prefetch" href="/assets/js/154.1309de49.js"><link rel="prefetch" href="/assets/js/155.81d3ee1f.js"><link rel="prefetch" href="/assets/js/156.154a4ef2.js"><link rel="prefetch" href="/assets/js/16.e5eb6147.js"><link rel="prefetch" href="/assets/js/17.57853c4a.js"><link rel="prefetch" href="/assets/js/18.cb9d7518.js"><link rel="prefetch" href="/assets/js/19.f354dc47.js"><link rel="prefetch" href="/assets/js/2.570d8a23.js"><link rel="prefetch" href="/assets/js/20.b5af7fad.js"><link rel="prefetch" href="/assets/js/21.0b1928fe.js"><link rel="prefetch" href="/assets/js/22.f78666de.js"><link rel="prefetch" href="/assets/js/23.29c3f366.js"><link rel="prefetch" href="/assets/js/24.6f596516.js"><link rel="prefetch" href="/assets/js/25.14067b60.js"><link rel="prefetch" href="/assets/js/26.74ba4989.js"><link rel="prefetch" href="/assets/js/27.13d60edd.js"><link rel="prefetch" href="/assets/js/28.9523cb32.js"><link rel="prefetch" href="/assets/js/29.8ec842e9.js"><link rel="prefetch" href="/assets/js/3.3fb3d2e0.js"><link rel="prefetch" href="/assets/js/30.805597a8.js"><link rel="prefetch" href="/assets/js/31.831b195d.js"><link rel="prefetch" href="/assets/js/32.063c672d.js"><link rel="prefetch" href="/assets/js/33.6d93fac3.js"><link rel="prefetch" href="/assets/js/34.56e8263c.js"><link rel="prefetch" href="/assets/js/35.dbe688bb.js"><link rel="prefetch" href="/assets/js/36.dc5af2c1.js"><link rel="prefetch" href="/assets/js/37.0a7494f6.js"><link rel="prefetch" href="/assets/js/38.fe4fc171.js"><link rel="prefetch" href="/assets/js/39.f5ed5e92.js"><link rel="prefetch" href="/assets/js/4.2c405ec8.js"><link rel="prefetch" href="/assets/js/40.fe7e2714.js"><link rel="prefetch" href="/assets/js/41.30b0811d.js"><link rel="prefetch" href="/assets/js/42.76f52d62.js"><link rel="prefetch" href="/assets/js/43.e7bb0817.js"><link rel="prefetch" href="/assets/js/44.ead0e883.js"><link rel="prefetch" href="/assets/js/45.235df046.js"><link rel="prefetch" href="/assets/js/46.5f09e829.js"><link rel="prefetch" href="/assets/js/47.67116354.js"><link rel="prefetch" href="/assets/js/48.31f34543.js"><link rel="prefetch" href="/assets/js/49.10b5ebba.js"><link rel="prefetch" href="/assets/js/5.6f47322c.js"><link rel="prefetch" href="/assets/js/50.c0f0b7f1.js"><link rel="prefetch" href="/assets/js/51.5143f3bf.js"><link rel="prefetch" href="/assets/js/52.eeddfd48.js"><link rel="prefetch" href="/assets/js/53.eb790db5.js"><link rel="prefetch" href="/assets/js/54.8fe5421c.js"><link rel="prefetch" href="/assets/js/55.d8f9004b.js"><link rel="prefetch" href="/assets/js/56.62ac9b92.js"><link rel="prefetch" href="/assets/js/57.a9caec0d.js"><link rel="prefetch" href="/assets/js/58.f93fc522.js"><link rel="prefetch" href="/assets/js/59.a81a03aa.js"><link rel="prefetch" href="/assets/js/6.8c2ea393.js"><link rel="prefetch" href="/assets/js/60.ab782775.js"><link rel="prefetch" href="/assets/js/61.6dd12daf.js"><link rel="prefetch" href="/assets/js/62.76f4b01f.js"><link rel="prefetch" href="/assets/js/64.6f8bb1fa.js"><link rel="prefetch" href="/assets/js/65.4120a44b.js"><link rel="prefetch" href="/assets/js/66.360c2d2b.js"><link rel="prefetch" href="/assets/js/67.26f84d32.js"><link rel="prefetch" href="/assets/js/68.68f45e5e.js"><link rel="prefetch" href="/assets/js/69.e311eb56.js"><link rel="prefetch" href="/assets/js/7.6762b2d7.js"><link rel="prefetch" href="/assets/js/70.cea82674.js"><link rel="prefetch" href="/assets/js/71.783ddcf7.js"><link rel="prefetch" href="/assets/js/72.e5467385.js"><link rel="prefetch" href="/assets/js/73.b8fb681b.js"><link rel="prefetch" href="/assets/js/74.1bae37db.js"><link rel="prefetch" href="/assets/js/75.024387e5.js"><link rel="prefetch" href="/assets/js/76.a8e53010.js"><link rel="prefetch" href="/assets/js/77.8c55500a.js"><link rel="prefetch" href="/assets/js/78.7ce90bf5.js"><link rel="prefetch" href="/assets/js/79.ef71713f.js"><link rel="prefetch" href="/assets/js/8.788a6364.js"><link rel="prefetch" href="/assets/js/80.acad589d.js"><link rel="prefetch" href="/assets/js/81.02670d10.js"><link rel="prefetch" href="/assets/js/82.53b7b1ac.js"><link rel="prefetch" href="/assets/js/83.99eb8581.js"><link rel="prefetch" href="/assets/js/84.d1535ce3.js"><link rel="prefetch" href="/assets/js/85.fe2b7de9.js"><link rel="prefetch" href="/assets/js/86.41850272.js"><link rel="prefetch" href="/assets/js/87.1cdc6df9.js"><link rel="prefetch" href="/assets/js/88.01bf3461.js"><link rel="prefetch" href="/assets/js/89.17c69819.js"><link rel="prefetch" href="/assets/js/9.3813842d.js"><link rel="prefetch" href="/assets/js/90.f6ae7e35.js"><link rel="prefetch" href="/assets/js/91.507bc284.js"><link rel="prefetch" href="/assets/js/92.90551782.js"><link rel="prefetch" href="/assets/js/93.dc442d78.js"><link rel="prefetch" href="/assets/js/94.315f4e94.js"><link rel="prefetch" href="/assets/js/95.ccd6c6bf.js"><link rel="prefetch" href="/assets/js/96.0c6d89d0.js"><link rel="prefetch" href="/assets/js/97.1a9f10a9.js"><link rel="prefetch" href="/assets/js/98.43be3caa.js"><link rel="prefetch" href="/assets/js/99.54c8207b.js">
    <link rel="stylesheet" href="/assets/css/0.styles.0dbae9ec.css">
  </head>
  <body>
    <div id="app" data-server-rendered="true"><div class="theme-container"><header class="navbar"><div class="sidebar-button"><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" role="img" viewBox="0 0 448 512" class="icon"><path fill="currentColor" d="M436 124H12c-6.627 0-12-5.373-12-12V80c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12zm0 160H12c-6.627 0-12-5.373-12-12v-32c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12zm0 160H12c-6.627 0-12-5.373-12-12v-32c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12z"></path></svg></div> <a href="/" class="home-link router-link-active"><!----> <span class="site-name">whoway</span></a> <div class="links" style="max-width:nullpx;"><div class="search-box"><input aria-label="Search" autocomplete="off" spellcheck="false" value=""> <!----></div> <nav class="nav-links can-hide"><div class="nav-item"><div class="dropdown-wrapper"><a class="dropdown-title"><span class="title">🎓Coding</span> <span class="arrow right"></span></a> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/00.Coding/TheBeautyOfProgramming/" class="nav-link">🔖编程之美题解</a></li><li class="dropdown-item"><!----> <a href="/00.Coding/CodeWarehouse/" class="nav-link">🔖代码意识流</a></li></ul></div></div><div class="nav-item"><div class="dropdown-wrapper"><a class="dropdown-title"><span class="title">🚀语言</span> <span class="arrow right"></span></a> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/01.Language/Overview/" class="nav-link">🔖概述</a></li><li class="dropdown-item"><!----> <a href="/01.Language/C/" class="nav-link">⭐️C</a></li><li class="dropdown-item"><!----> <a href="/01.Language/Cpp/" class="nav-link">🚀C++</a></li><li class="dropdown-item"><!----> <a href="/01.Language/Java/" class="nav-link">☕️Java</a></li><li class="dropdown-item"><!----> <a href="/01.Language/Python/" class="nav-link">🧩Python3</a></li></ul></div></div><div class="nav-item"><a href="/02.Hardware/" class="nav-link">✔️硬件基础</a></div><div class="nav-item"><div class="dropdown-wrapper"><a class="dropdown-title"><span class="title">⭐️软件基础</span> <span class="arrow right"></span></a> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/03.Software/01.DataStructureAndAlgorithm/" class="nav-link router-link-active">🐾数据结构和算法</a></li><li class="dropdown-item"><!----> <a href="/03.Software/02.OS/" class="nav-link">💻操作系统</a></li><li class="dropdown-item"><!----> <a href="/03.Software/03.Net/" class="nav-link">☁️计算机网络</a></li><li class="dropdown-item"><!----> <a href="/03.Software/04.SE/" class="nav-link">✅软件工程</a></li></ul></div></div><div class="nav-item"><a href="/04.Database/" class="nav-link">🎨数据库</a></div><div class="nav-item"><a href="/05.Engineer/" class="nav-link">🔖学术/工程</a></div><div class="nav-item"><div class="dropdown-wrapper"><a class="dropdown-title"><span class="title">⚙️工具</span> <span class="arrow right"></span></a> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/06.Tools/01.employment/" class="nav-link">🔖求职</a></li><li class="dropdown-item"><!----> <a href="/06.Tools/02.efficiency/" class="nav-link">🚀效能</a></li><li class="dropdown-item"><!----> <a href="/06.Tools/03.windows/" class="nav-link">⚙️Windows</a></li><li class="dropdown-item"><!----> <a href="/06.Tools/04.design/" class="nav-link">🧩设计</a></li><li class="dropdown-item"><!----> <a href="/06.Tools/05.linux/" class="nav-link">🐉Linux</a></li></ul></div></div><div class="nav-item"><a href="https://github.com/whoway" target="_blank" rel="noopener noreferrer" class="nav-link external">
  GitHub
  <svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg></a></div> <!----></nav></div></header> <div class="sidebar-mask"></div> <div class="sidebar"><nav class="nav-links"><div class="nav-item"><div class="dropdown-wrapper"><a class="dropdown-title"><span class="title">🎓Coding</span> <span class="arrow right"></span></a> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/00.Coding/TheBeautyOfProgramming/" class="nav-link">🔖编程之美题解</a></li><li class="dropdown-item"><!----> <a href="/00.Coding/CodeWarehouse/" class="nav-link">🔖代码意识流</a></li></ul></div></div><div class="nav-item"><div class="dropdown-wrapper"><a class="dropdown-title"><span class="title">🚀语言</span> <span class="arrow right"></span></a> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/01.Language/Overview/" class="nav-link">🔖概述</a></li><li class="dropdown-item"><!----> <a href="/01.Language/C/" class="nav-link">⭐️C</a></li><li class="dropdown-item"><!----> <a href="/01.Language/Cpp/" class="nav-link">🚀C++</a></li><li class="dropdown-item"><!----> <a href="/01.Language/Java/" class="nav-link">☕️Java</a></li><li class="dropdown-item"><!----> <a href="/01.Language/Python/" class="nav-link">🧩Python3</a></li></ul></div></div><div class="nav-item"><a href="/02.Hardware/" class="nav-link">✔️硬件基础</a></div><div class="nav-item"><div class="dropdown-wrapper"><a class="dropdown-title"><span class="title">⭐️软件基础</span> <span class="arrow right"></span></a> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/03.Software/01.DataStructureAndAlgorithm/" class="nav-link router-link-active">🐾数据结构和算法</a></li><li class="dropdown-item"><!----> <a href="/03.Software/02.OS/" class="nav-link">💻操作系统</a></li><li class="dropdown-item"><!----> <a href="/03.Software/03.Net/" class="nav-link">☁️计算机网络</a></li><li class="dropdown-item"><!----> <a href="/03.Software/04.SE/" class="nav-link">✅软件工程</a></li></ul></div></div><div class="nav-item"><a href="/04.Database/" class="nav-link">🎨数据库</a></div><div class="nav-item"><a href="/05.Engineer/" class="nav-link">🔖学术/工程</a></div><div class="nav-item"><div class="dropdown-wrapper"><a class="dropdown-title"><span class="title">⚙️工具</span> <span class="arrow right"></span></a> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/06.Tools/01.employment/" class="nav-link">🔖求职</a></li><li class="dropdown-item"><!----> <a href="/06.Tools/02.efficiency/" class="nav-link">🚀效能</a></li><li class="dropdown-item"><!----> <a href="/06.Tools/03.windows/" class="nav-link">⚙️Windows</a></li><li class="dropdown-item"><!----> <a href="/06.Tools/04.design/" class="nav-link">🧩设计</a></li><li class="dropdown-item"><!----> <a href="/06.Tools/05.linux/" class="nav-link">🐉Linux</a></li></ul></div></div><div class="nav-item"><a href="https://github.com/whoway" target="_blank" rel="noopener noreferrer" class="nav-link external">
  GitHub
  <svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg></a></div> <!----></nav>  <ul class="sidebar-links"><li><div class="sidebar-group first"><p class="sidebar-heading open"><span>DP动态规划</span> <!----></p> <ul class="sidebar-group-items"><li><a href="/03.Software/01.DataStructureAndAlgorithm/SkillLibrary/Part04.%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%E6%8A%80%E5%B7%A7.html#📑-目录" class="sidebar-link">📑 目录</a><ul class="sidebar-sub-headers"></ul></li><li><a href="/03.Software/01.DataStructureAndAlgorithm/SkillLibrary/Part04.%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%E6%8A%80%E5%B7%A7.html#✅动态规划思考模板" class="sidebar-link">✅动态规划思考模板</a><ul class="sidebar-sub-headers"></ul></li><li><a href="/03.Software/01.DataStructureAndAlgorithm/SkillLibrary/Part04.%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%E6%8A%80%E5%B7%A7.html#_01-dp前置知识『找规律技巧』" class="sidebar-link">01.dp前置知识『找规律技巧』</a><ul class="sidebar-sub-headers"><li class="sidebar-sub-header"><a href="/03.Software/01.DataStructureAndAlgorithm/SkillLibrary/Part04.%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%E6%8A%80%E5%B7%A7.html#_1-1借助oj设计原理技巧，输出编号" class="sidebar-link">1.1借助OJ设计原理技巧，输出编号</a></li><li class="sidebar-sub-header"><a href="/03.Software/01.DataStructureAndAlgorithm/SkillLibrary/Part04.%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%E6%8A%80%E5%B7%A7.html#_1-2-技巧的使用案例" class="sidebar-link">1.2.技巧的使用案例</a></li></ul></li><li><a href="/03.Software/01.DataStructureAndAlgorithm/SkillLibrary/Part04.%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%E6%8A%80%E5%B7%A7.html#_02-dp基础⭐️" class="sidebar-link">02.dp基础⭐️</a><ul class="sidebar-sub-headers"><li class="sidebar-sub-header"><a href="/03.Software/01.DataStructureAndAlgorithm/SkillLibrary/Part04.%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%E6%8A%80%E5%B7%A7.html#_2-1-适用情况" class="sidebar-link">2.1.适用情况</a></li><li class="sidebar-sub-header"><a href="/03.Software/01.DataStructureAndAlgorithm/SkillLibrary/Part04.%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%E6%8A%80%E5%B7%A7.html#_2-2-动态规划解题的『一般思路』" class="sidebar-link">2.2.动态规划解题的『一般思路』</a></li><li class="sidebar-sub-header"><a href="/03.Software/01.DataStructureAndAlgorithm/SkillLibrary/Part04.%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%E6%8A%80%E5%B7%A7.html#_2-3-动态规划思考和答疑" class="sidebar-link">2.3.动态规划思考和答疑</a></li></ul></li><li><a href="/03.Software/01.DataStructureAndAlgorithm/SkillLibrary/Part04.%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%E6%8A%80%E5%B7%A7.html#_03-dp的启发性思维导图" class="sidebar-link">03.DP的启发性思维导图</a><ul class="sidebar-sub-headers"></ul></li><li><a href="/03.Software/01.DataStructureAndAlgorithm/SkillLibrary/Part04.%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%E6%8A%80%E5%B7%A7.html#🍁参考资料" class="sidebar-link">🍁参考资料</a><ul class="sidebar-sub-headers"></ul></li></ul></div></li></ul> </div> <div class="page"> <div class="content"><h1 id="dp动态规划"><a href="#dp动态规划" class="header-anchor">#</a> DP动态规划</h1> <div class="language-txt line-numbers-mode"><pre class="language-text"><code>&lt;font style=&quot;background:yellow&quot;&gt;
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br></div></div><ul><li>01.DP和数学找规律题的区别</li> <li>02.dp的递归写法、迭代写法</li> <li>03.背包九讲阅读</li></ul> <div class="language-txt line-numbers-mode"><pre class="language-text"><code>参考OI进行分类
1）记忆化搜索
2）背包 DP  
3）区间 DP
4）树形 DP
5）DAG 上的 DP
6）状压 DP
7）数位 DP
8）插头 DP  
9）计数 DP  
10）动态 DP  
11）DP 优化   
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br></div></div><h2 id="📑-目录"><a href="#📑-目录" class="header-anchor">#</a> 📑 目录</h2> <p>[TOC]</p> <h2 id="✅动态规划思考模板"><a href="#✅动态规划思考模板" class="header-anchor">#</a> ✅动态规划思考模板</h2> <ul><li>1、确定『状态』和『选择』：<font style="background:yellow;">容易</font> <ul><li>状态：如何才能描述一个问题的局面？也就是会发生变化的『变量』</li> <li>选择：每一步要做的决定</li></ul></li> <li>2、确定dp【状态1】【状态2】【状态3】。。。数组的意义</li> <li>3、根据“选择”，思考状态转移的逻辑
<ul><li>确定Base问题，如何初始化</li></ul></li> <li>4、『自己决定要不要优化』</li></ul> <h2 id="_01-dp前置知识『找规律技巧』"><a href="#_01-dp前置知识『找规律技巧』" class="header-anchor">#</a> 01.dp前置知识『找规律技巧』</h2> <h3 id="_1-1借助oj设计原理技巧，输出编号"><a href="#_1-1借助oj设计原理技巧，输出编号" class="header-anchor">#</a> 1.1借助OJ设计原理技巧，输出编号</h3> <ul><li>Tips:<code>in.txt</code>和<code>out.txt</code>都和你运行的程序在同一当前目录</li> <li>首先，我创建in.txt作为，我存入输入数据</li> <li>其次，我可以建立out.txt，也可不建立</li></ul> <h4 id="_1-1-1-模板如下"><a href="#_1-1-1-模板如下" class="header-anchor">#</a> 1.1.1.模板如下</h4> <div class="language-cpp line-numbers-mode"><pre class="language-cpp"><code><span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span><span class="token string">&lt;stdio.h&gt;</span></span>

<span class="token keyword">int</span> <span class="token function">main</span><span class="token punctuation">(</span><span class="token punctuation">)</span>
<span class="token punctuation">{</span>
	FILE <span class="token operator">*</span> fp_in<span class="token punctuation">;</span>
	FILE <span class="token operator">*</span> fp_out<span class="token punctuation">;</span>
    <span class="token comment">//输入文件，&quot;r+&quot;用读/写方式，打开一个（已存在）的文件</span>
	fp_in<span class="token operator">=</span><span class="token function">fopen</span><span class="token punctuation">(</span><span class="token string">&quot;in.txt&quot;</span><span class="token punctuation">,</span><span class="token string">&quot;r+&quot;</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    
    <span class="token comment">//输出文件，&quot;w+&quot;表示，用读/写方式，（建立）一个新的文本文件</span>
    <span class="token comment">//PS：其实，要是我原先建好了out.txt也行。</span>
	fp_out<span class="token operator">=</span><span class="token function">fopen</span><span class="token punctuation">(</span><span class="token string">&quot;out.txt&quot;</span><span class="token punctuation">,</span><span class="token string">&quot;w+&quot;</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    
	
	<span class="token keyword">if</span><span class="token punctuation">(</span><span class="token constant">NULL</span><span class="token operator">==</span>fp_in<span class="token punctuation">)</span>
	<span class="token punctuation">{</span>
		<span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">&quot;NO&quot;</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
	<span class="token punctuation">}</span>
	<span class="token keyword">else</span>
	<span class="token punctuation">{</span>
		<span class="token keyword">int</span> a<span class="token punctuation">,</span>b<span class="token punctuation">,</span>c<span class="token punctuation">;</span>
		<span class="token keyword">int</span> i<span class="token operator">=</span><span class="token number">1</span><span class="token punctuation">;</span><span class="token comment">//用于编号 </span>
        
        <span class="token comment">//这是对文件中的字符，用格式&quot;%d%d%d&quot;扫描进来。</span>
		<span class="token keyword">while</span><span class="token punctuation">(</span><span class="token operator">~</span><span class="token function">fscanf</span><span class="token punctuation">(</span>fp_in<span class="token punctuation">,</span><span class="token string">&quot;%d%d%d&quot;</span><span class="token punctuation">,</span><span class="token operator">&amp;</span>a<span class="token punctuation">,</span><span class="token operator">&amp;</span>b<span class="token punctuation">,</span><span class="token operator">&amp;</span>c<span class="token punctuation">)</span><span class="token punctuation">)</span>
		<span class="token punctuation">{</span>
			<span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">&quot;%d %d %d\n&quot;</span><span class="token punctuation">,</span>a<span class="token punctuation">,</span>b<span class="token punctuation">,</span>c<span class="token punctuation">)</span><span class="token punctuation">;</span>
			<span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">&quot;n=%d sum=%d\n&quot;</span><span class="token punctuation">,</span>i<span class="token punctuation">,</span>a<span class="token operator">+</span>b<span class="token operator">+</span>c<span class="token punctuation">)</span><span class="token punctuation">;</span><span class="token comment">//编号 </span>
			<span class="token function">fprintf</span><span class="token punctuation">(</span>fp_out<span class="token punctuation">,</span><span class="token string">&quot;n=%d sum=%d\n&quot;</span><span class="token punctuation">,</span>i<span class="token operator">++</span><span class="token punctuation">,</span>a<span class="token operator">+</span>b<span class="token operator">+</span>c<span class="token punctuation">)</span><span class="token punctuation">;</span>
		<span class="token punctuation">}</span>
		
	<span class="token punctuation">}</span>
	
	
	
	<span class="token function">fclose</span><span class="token punctuation">(</span>fp_in<span class="token punctuation">)</span><span class="token punctuation">;</span><span class="token comment">//关闭输入文件</span>
	<span class="token function">fclose</span><span class="token punctuation">(</span>fp_out<span class="token punctuation">)</span><span class="token punctuation">;</span><span class="token comment">//关闭输出文件</span>
	<span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span>
 <span class="token punctuation">}</span> 


</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br><span class="line-number">17</span><br><span class="line-number">18</span><br><span class="line-number">19</span><br><span class="line-number">20</span><br><span class="line-number">21</span><br><span class="line-number">22</span><br><span class="line-number">23</span><br><span class="line-number">24</span><br><span class="line-number">25</span><br><span class="line-number">26</span><br><span class="line-number">27</span><br><span class="line-number">28</span><br><span class="line-number">29</span><br><span class="line-number">30</span><br><span class="line-number">31</span><br><span class="line-number">32</span><br><span class="line-number">33</span><br><span class="line-number">34</span><br><span class="line-number">35</span><br><span class="line-number">36</span><br><span class="line-number">37</span><br><span class="line-number">38</span><br><span class="line-number">39</span><br><span class="line-number">40</span><br><span class="line-number">41</span><br></div></div><blockquote><p>Tips:测试样例</p></blockquote> <ul><li>1.1.2.第一种输入，in.txt（我习惯用这样的）</li></ul> <div class="language-cpp line-numbers-mode"><pre class="language-cpp"><code><span class="token number">1</span> <span class="token number">3</span> <span class="token number">5</span> 
<span class="token number">2</span> <span class="token number">6</span> <span class="token number">10</span>
<span class="token number">4</span> <span class="token number">12</span> <span class="token number">20</span>

<span class="token comment">//in.txt</span>
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br></div></div><ul><li>1.1.3.第二种输入<code>in.txt</code>（这样也行）</li></ul> <div class="language-cpp line-numbers-mode"><pre class="language-cpp"><code><span class="token number">1</span> <span class="token number">3</span> <span class="token number">5</span> <span class="token number">2</span> <span class="token number">6</span> <span class="token number">10</span>
<span class="token number">4</span> <span class="token number">12</span> <span class="token number">20</span>

<span class="token comment">//in.txt</span>
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br></div></div><ul><li>1.1.4.输出的<code>out.txt</code></li></ul> <div class="language-cpp line-numbers-mode"><pre class="language-cpp"><code>n<span class="token operator">=</span><span class="token number">1</span> sum<span class="token operator">=</span><span class="token number">9</span>
n<span class="token operator">=</span><span class="token number">2</span> sum<span class="token operator">=</span><span class="token number">18</span>
n<span class="token operator">=</span><span class="token number">3</span> sum<span class="token operator">=</span><span class="token number">36</span>
    
<span class="token comment">//out.txt</span>
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br></div></div><h3 id="_1-2-技巧的使用案例"><a href="#_1-2-技巧的使用案例" class="header-anchor">#</a> 1.2.技巧的使用案例</h3> <h4 id="_1-2-1-例1：xor-sum"><a href="#_1-2-1-例1：xor-sum" class="header-anchor">#</a> 1.2.1.例1：XOR sum</h4> <ul><li><p>（不是动态规划）</p></li> <li><p>考察知识点：<code>前缀和，位运算</code></p></li> <li><p>湖南大学程序设计竞赛新生赛 <code>M题</code> <a href="https://ac.nowcoder.com/acm/contest/3674/M" target="_blank" rel="noopener noreferrer">XOR sum<svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg></a></p></li> <li><p>小范围暴力找规律，规律当结论记住`</p></li></ul> <div class="language-cpp line-numbers-mode"><pre class="language-cpp"><code>题目描述 
You are given two positive integers l <span class="token operator">and</span> r<span class="token punctuation">,</span>you shoud answer l⊕<span class="token punctuation">(</span>l<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">)</span>⊕<span class="token punctuation">.</span><span class="token punctuation">.</span><span class="token punctuation">.</span>⊕r<span class="token punctuation">,</span>where ⊕ denotes the bitwise XOR operation<span class="token punctuation">.</span> In XOR operation we perform the comparison of two bits<span class="token punctuation">,</span> being <span class="token number">1</span> <span class="token keyword">if</span> the two bits are different<span class="token punctuation">,</span> <span class="token operator">and</span> <span class="token number">0</span> <span class="token keyword">if</span> they are the same<span class="token punctuation">.</span> 
For example<span class="token operator">:</span>

输入描述<span class="token operator">:</span>
The input contain two integers l <span class="token punctuation">,</span><span class="token function">r</span> <span class="token punctuation">(</span><span class="token number">1</span> ≤ l ≤ r ≤<span class="token number">1018</span><span class="token punctuation">)</span> 
输出描述<span class="token operator">:</span>
The only output line should contain a single integer

示例<span class="token number">1</span>
输入
<span class="token number">1</span> <span class="token number">2</span>
输出
<span class="token number">3</span>
说明
<span class="token number">1</span>⊕<span class="token number">2</span><span class="token operator">=</span><span class="token number">3</span>

示例<span class="token number">2</span>
输入
<span class="token number">3</span> <span class="token number">6</span>
输出
<span class="token number">4</span>
说明
<span class="token number">3</span>⊕<span class="token number">4</span>⊕<span class="token number">5</span>⊕<span class="token number">6</span><span class="token operator">=</span><span class="token number">4</span>
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br><span class="line-number">17</span><br><span class="line-number">18</span><br><span class="line-number">19</span><br><span class="line-number">20</span><br><span class="line-number">21</span><br><span class="line-number">22</span><br><span class="line-number">23</span><br><span class="line-number">24</span><br></div></div><ul><li>『1。。思路：』</li></ul> <p>1）想法1：首先看到能够很明显模拟的，那么首先就会想到暴力，但是会发现<code>TLE</code><br>
2）想法2：这样，很有规律但是超时的，那么可能是**<code>规律题</code><strong>，或者可能是</strong><code>动态规划</code><strong>，<br>
那么问题转换为</strong><code>如何找规律</code><strong>，或者</strong><code>如何找状态转移方程</code>**</p> <ul><li>『2。。做法』</li></ul> <p>1)首先创建测试数据，为了避免手工输入测试数据太慢，也避免测试数据太少，无法找出规律，所以，我写了代码生成<code>in.txt</code></p> <div class="language-cpp line-numbers-mode"><pre class="language-cpp"><code><span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span><span class="token string">&lt;cstdio&gt;</span></span>

<span class="token keyword">int</span> <span class="token function">main</span><span class="token punctuation">(</span><span class="token punctuation">)</span>
<span class="token punctuation">{</span>
	FILE <span class="token operator">*</span> fp_in<span class="token punctuation">;</span>
	fp_in<span class="token operator">=</span><span class="token function">fopen</span><span class="token punctuation">(</span><span class="token string">&quot;in.txt&quot;</span><span class="token punctuation">,</span><span class="token string">&quot;w+&quot;</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
	
	<span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i<span class="token operator">=</span><span class="token number">1</span><span class="token punctuation">;</span>i<span class="token operator">&lt;</span><span class="token number">101</span><span class="token punctuation">;</span><span class="token operator">++</span>i<span class="token punctuation">)</span>
	<span class="token punctuation">{</span>
		<span class="token function">fprintf</span><span class="token punctuation">(</span>fp_in<span class="token punctuation">,</span><span class="token string">&quot;1 %d\n&quot;</span><span class="token punctuation">,</span>i<span class="token punctuation">)</span><span class="token punctuation">;</span>
	<span class="token punctuation">}</span>
	
	<span class="token function">fclose</span><span class="token punctuation">(</span>fp_in<span class="token punctuation">)</span><span class="token punctuation">;</span>
	<span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br></div></div><ul><li>生成的<code>in.txt</code>中，有形如这样的</li></ul> <div class="language-in.txt line-numbers-mode"><pre class="language-text"><code>1 1
1 2
1 3
1 4
1 5
省略-——注意，这不是文件中的
1 100
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br></div></div><p>2)准备数据进行小范围的OJ模拟<br>
代码</p> <div class="language-cpp line-numbers-mode"><pre class="language-cpp"><code><span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span><span class="token string">&lt;cstdio&gt;</span></span>

<span class="token keyword">int</span> <span class="token function">main</span><span class="token punctuation">(</span><span class="token punctuation">)</span>
<span class="token punctuation">{</span>
	FILE <span class="token operator">*</span> fp_in<span class="token punctuation">;</span>
	FILE <span class="token operator">*</span> fp_out<span class="token punctuation">;</span>
	fp_in<span class="token operator">=</span><span class="token function">fopen</span><span class="token punctuation">(</span><span class="token string">&quot;in.txt&quot;</span><span class="token punctuation">,</span><span class="token string">&quot;r+&quot;</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
	fp_out<span class="token operator">=</span><span class="token function">fopen</span><span class="token punctuation">(</span><span class="token string">&quot;out.txt&quot;</span><span class="token punctuation">,</span><span class="token string">&quot;w+&quot;</span><span class="token punctuation">)</span><span class="token punctuation">;</span>	
	
	<span class="token keyword">unsigned</span> <span class="token keyword">int</span> a<span class="token punctuation">,</span>b<span class="token punctuation">;</span>
	
	<span class="token keyword">int</span> n<span class="token operator">=</span><span class="token number">1</span><span class="token punctuation">;</span>
	
	<span class="token keyword">while</span><span class="token punctuation">(</span><span class="token operator">~</span><span class="token function">fscanf</span><span class="token punctuation">(</span>fp_in<span class="token punctuation">,</span><span class="token string">&quot;%u%u&quot;</span><span class="token punctuation">,</span><span class="token operator">&amp;</span>a<span class="token punctuation">,</span><span class="token operator">&amp;</span>b<span class="token punctuation">)</span><span class="token punctuation">)</span>
	<span class="token punctuation">{</span>
		<span class="token keyword">unsigned</span> sum<span class="token operator">=</span>a<span class="token punctuation">;</span>
		<span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">unsigned</span> <span class="token keyword">int</span> i<span class="token operator">=</span><span class="token punctuation">(</span>a<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">;</span>i<span class="token operator">&lt;=</span>b<span class="token punctuation">;</span><span class="token operator">++</span>i<span class="token punctuation">)</span>
		<span class="token punctuation">{</span>
			sum<span class="token operator">^=</span>i<span class="token punctuation">;</span>
		<span class="token punctuation">}</span>
		
		<span class="token function">fprintf</span><span class="token punctuation">(</span>fp_out<span class="token punctuation">,</span><span class="token string">&quot;%d-%d ==%d\n&quot;</span><span class="token punctuation">,</span>a<span class="token punctuation">,</span>b<span class="token punctuation">,</span>sum<span class="token punctuation">)</span><span class="token punctuation">;</span>
	<span class="token punctuation">}</span>
		
		

	
	<span class="token function">fclose</span><span class="token punctuation">(</span>fp_in<span class="token punctuation">)</span><span class="token punctuation">;</span>
	<span class="token function">fclose</span><span class="token punctuation">(</span>fp_out<span class="token punctuation">)</span><span class="token punctuation">;</span>
	<span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br><span class="line-number">17</span><br><span class="line-number">18</span><br><span class="line-number">19</span><br><span class="line-number">20</span><br><span class="line-number">21</span><br><span class="line-number">22</span><br><span class="line-number">23</span><br><span class="line-number">24</span><br><span class="line-number">25</span><br><span class="line-number">26</span><br><span class="line-number">27</span><br><span class="line-number">28</span><br><span class="line-number">29</span><br><span class="line-number">30</span><br><span class="line-number">31</span><br></div></div><p>模拟出out.txt</p> <div class="language-out.txt line-numbers-mode"><pre class="language-text"><code>1-1 ==1
1-2 ==3
1-3 ==0
1-4 ==4
1-5 ==1
1-6 ==7
1-7 ==0
1-8 ==8
1-9 ==1
1-10 ==11
1-11 ==0
1-12 ==12
1-13 ==1
1-14 ==15
1-15 ==0
1-16 ==16
1-17 ==1
1-18 ==19
1-19 ==0
1-20 ==20
1-21 ==1
1-22 ==23
1-23 ==0
省略-——注意，这不是文件中的
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br><span class="line-number">17</span><br><span class="line-number">18</span><br><span class="line-number">19</span><br><span class="line-number">20</span><br><span class="line-number">21</span><br><span class="line-number">22</span><br><span class="line-number">23</span><br><span class="line-number">24</span><br></div></div><p>显然，有比较明显的规律如下图</p> <p><img src="https://cdn.jsdelivr.net/gh/HACV/picture/img/2020_07_03_DP_Series_One_01.png" alt="2020_07_03_DP_Series_One_01"></p> <ul><li>至此，我们发现了1-num的规律，由于规律太明显，不经让人大胆的猜测，其他形如2-num，3-num可能都只与
区间[left,right]的right有关，但是我们要严谨，毕竟，现在暴力模拟的只是<code>left=1</code>的场景</li></ul> <h4 id="_3）《一》常规方式"><a href="#_3）《一》常规方式" class="header-anchor">#</a> 3）《一》常规方式</h4> <p>（虽然技巧性没有那么强，但是比较通用）<br>
我们可以有两种做法，但是其实都是殊途同归<br>
1）直接用这个模拟，然后，我们手算测试2-num，3-num。差不多的话，那就比较肯定是这个规律<br>
1）模拟2-num,模拟3-num等，综合几组找规律<br>
但是，由示例2的3-6发现，也并不满足这个规律，第1种比较碰运气的不行。<br>
但是由于有这么明显的规律，那么我们不妨用第2种做法，我们还是很相信，最后结果和left可能也有关。</p> <p>再次暴力模拟</p> <div class="language-out.txt line-numbers-mode"><pre class="language-text"><code>2-2 ==2
2-3 ==1
2-4 ==5
2-5 ==0
2-6 ==6
2-7 ==1
2-8 ==9
2-9 ==0
2-10 ==10
2-11 ==1
2-12 ==13
2-13 ==0
2-14 ==14
2-15 ==1
省略----
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br></div></div><p>显然，又是4个一组<br>
并且又是下面这样的规律，但是却和1-num的编号，对不上。</p> <div class="language-txt line-numbers-mode"><pre class="language-text"><code>num
1
num+1
0
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br></div></div><p>模拟3-num</p> <div class="language-txt line-numbers-mode"><pre class="language-text"><code>3-3 ==3
3-4 ==7
3-5 ==2
3-6 ==4
3-7 ==3
3-8 ==11
3-9 ==2
3-10 ==8
3-11 ==3
3-12 ==15
3-13 ==2
3-14 ==12
3-15 ==3
3-16 ==19
3-17 ==2
3-18 ==16
3-19 ==3
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br><span class="line-number">17</span><br></div></div><p>继续模拟，省略。。。后续，我对照<br>
尴尬的。。。我没有找出规律。所以，我后面用的下面技巧性的方法想出来的。</p> <h4 id="_4）《二》技巧性的方法"><a href="#_4）《二》技巧性的方法" class="header-anchor">#</a> 4）《二》技巧性的方法</h4> <p>至此，懒得再次模拟，可以借助我以前写代码，比如说前n项和等开放的思维。<br>
我就想，如何将[left,right]和[1,right]联系起来？</p> <p>后来，笔者观察到的是这样的规律：<br>
我们假设，$f(n)$表示[1,right]的异或和<br>
那么，我们观察到<br>
$f(3)=1^2^3$
$f(5)=1^2^3^4^5$
要是，我们想要求[3,5]的异或和<br>
也就是求$f=3^4^5$
我们的目标就转换为，如何由前面两个式子弄成现在这个式子的样子<br>
我首先想到的是，可以类似除法的话
那么，我需要的式子应该是
$f(2)=1^2$
$f(5)=1^2^3^4^5$
但是，又不能直接和除法一样除，灵机一转，那我从异或的角度来思考
异或规则：</p> <div class="language-txt line-numbers-mode"><pre class="language-text"><code>0^1=1
0^0=0
1^0=1
1^1=0
相同则为0，不同则为1
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br></div></div><p>如何才能将前面的$1^2$去掉呢，并且还不能影响到后面的呢<br>
由异或的规则前两行，我们发现，0和k=0,1或都等于k<br>
其实是如何求<br>
$f=3^4^5$就可以转换为$f=0^3^4^5$
但是，问题又来了，前面的0如何构造。<br>
灵机一转，任何两个相同的数字，异或永远是0。
那么，求$f=3^4^5$就可以转换为$f（3-1）^f（5）$</p> <h4 id="_5）最终代码"><a href="#_5）最终代码" class="header-anchor">#</a> 5）最终代码</h4> <div class="language-cpp line-numbers-mode"><pre class="language-cpp"><code><span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span><span class="token string">&lt;cstdio&gt;</span></span>

<span class="token keyword">unsigned</span> <span class="token keyword">long</span> <span class="token keyword">long</span> <span class="token function">solution</span><span class="token punctuation">(</span><span class="token keyword">unsigned</span> <span class="token keyword">long</span> <span class="token keyword">long</span>  n<span class="token punctuation">)</span>
<span class="token punctuation">{</span>
	<span class="token keyword">if</span><span class="token punctuation">(</span>n<span class="token operator">%</span><span class="token number">4</span><span class="token operator">==</span><span class="token number">0</span><span class="token punctuation">)</span>
		<span class="token keyword">return</span> n<span class="token punctuation">;</span>
	<span class="token keyword">else</span> <span class="token keyword">if</span><span class="token punctuation">(</span>n<span class="token operator">%</span><span class="token number">4</span><span class="token operator">==</span><span class="token number">1</span><span class="token punctuation">)</span>
		<span class="token keyword">return</span> <span class="token number">1</span><span class="token punctuation">;</span>
	<span class="token keyword">else</span> <span class="token keyword">if</span><span class="token punctuation">(</span>n<span class="token operator">%</span><span class="token number">4</span><span class="token operator">==</span><span class="token number">2</span><span class="token punctuation">)</span>
		<span class="token keyword">return</span> n<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">;</span>
	<span class="token keyword">else</span> <span class="token keyword">if</span><span class="token punctuation">(</span>n<span class="token operator">%</span><span class="token number">4</span><span class="token operator">==</span><span class="token number">3</span><span class="token punctuation">)</span>
		<span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>

<span class="token keyword">int</span> <span class="token function">main</span><span class="token punctuation">(</span><span class="token keyword">void</span><span class="token punctuation">)</span>
<span class="token punctuation">{</span>
	<span class="token keyword">unsigned</span> <span class="token keyword">long</span> <span class="token keyword">long</span> a<span class="token punctuation">,</span>b<span class="token punctuation">;</span>
	<span class="token comment">//注意，是正整数，然后，我先前只考虑的unsigned int，只通过了0.8样例</span>
    <span class="token comment">//后来发现，，，对了，unsigned long long。我怎么先前就假设别人要的unsigned int 呢</span>
	<span class="token keyword">while</span><span class="token punctuation">(</span><span class="token operator">~</span><span class="token function">scanf</span><span class="token punctuation">(</span><span class="token string">&quot;%lld%lld&quot;</span><span class="token punctuation">,</span><span class="token operator">&amp;</span>a<span class="token punctuation">,</span><span class="token operator">&amp;</span>b<span class="token punctuation">)</span><span class="token punctuation">)</span>
	<span class="token punctuation">{</span>
		<span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">&quot;%lld\n&quot;</span><span class="token punctuation">,</span><span class="token function">solution</span><span class="token punctuation">(</span>a<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">)</span><span class="token operator">^</span><span class="token function">solution</span><span class="token punctuation">(</span>b<span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
	<span class="token punctuation">}</span>

	<span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span> 
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br><span class="line-number">17</span><br><span class="line-number">18</span><br><span class="line-number">19</span><br><span class="line-number">20</span><br><span class="line-number">21</span><br><span class="line-number">22</span><br><span class="line-number">23</span><br><span class="line-number">24</span><br><span class="line-number">25</span><br><span class="line-number">26</span><br></div></div><h4 id="_1-2-2-例2：统计累加算式"><a href="#_1-2-2-例2：统计累加算式" class="header-anchor">#</a> 1.2.2.例2：统计累加算式</h4> <ul><li>（可以说是规律题，也可以说是dp题）</li> <li>来源：深信服校园招聘<code>c/c++</code>软件开发D卷 <a href="https://www.nowcoder.com/questionTerminal/6ec6dbe36bc84e91b0eea012446a44cc" target="_blank" rel="noopener noreferrer">统计累加算式<svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg></a></li> <li>也有来源说是 整数分解为2的幂 清华复试</li> <li>考察知识点：<code>分区（数论）</code></li></ul> <p>示例1</p> <div class="language-txt line-numbers-mode"><pre class="language-text"><code>输入
7
输出
6
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br></div></div><h4 id="_1）思路"><a href="#_1）思路" class="header-anchor">#</a> 1）思路</h4> <p>1）首先，想到暴力进行模拟，利用数组，下表i表示2的i次方，用数组值模拟个数。但是这种的搜索空间太大了
比如，题干举例的7，在<code>1+1+1+4</code>和<code>1+2+2+2</code>，显然，我们直接从全1，慢慢合并到最终的<code>1+2+4</code>，其中我们还需要进行回溯。比较麻烦，也比较容易超时。
2）从以前阅读的《具体数学》书中启发的，我们对于这种很有可能有规律的，进行找规律
3）进一步的，其实，我们方法1）是从全1开始合并到最终，那么我们可以反过来思考。从那个数字本身对应的二进制位，每个权，一步步分解，直到全1，这个其实也要回溯，但是这样反着分解，似乎有些猫腻。（具体见下）</p> <h4 id="_2）找规律"><a href="#_2）找规律" class="header-anchor">#</a> 2）找规律</h4> <p>手工模拟，分解
1的分解方法 有1种
<code>1=1</code>
2的分解方法 有2种
<code>2=1+1</code> <code>2</code>
3的分解方法 有2种
4的分解方法 有4种
5的分解方法 有4种
6的分解方法 有6种
7的分解方法 有6种</p> <p>至此，我就已经发现比较显然的几种可能的规律：
1）很肯定的规律：$f(2m+1)=f(2m)$（m=1,2,3...n)
2)猜测1：$f(2m)=2m$（m=1,2,3...n)
3)猜测2：$f(2m)=f((2m)/2)+f(2m-1)=f(m)+f(2m-1)$（m=1,2,3...n)</p> <p>为什么说，规律1）我很肯定呢，因为，我做出猜测之后，能够很容易的证明这个猜想是对的
Reason：我们知道奇数的二进制的最低位肯定是1，偶数则是0
由此，我们知道，比起偶数，比他大1的相邻的奇数，肯定最后那个1无法合并，一直放在各个分解的式子末尾，所以不影响分解方法数目。</p> <p>验证，猜测1）
我们将8进行分解
<code>1+1+1+1+1+1+1+1</code> <code>1+1+1+1+1+1+2</code> <code>1+1+1+1+2+2</code> <code>1+1+2+2+2</code> <code>2+2+2+2</code> <code>2+2+4</code> <code>4+4</code> <code>8</code>
此外，我们回溯，1+1+1+1+2+2h还有
<code>1+1+1+1+4</code> <code>1+1+2+4</code>
有10种
猜测1错误</p> <p>验证，猜测2）
从验证猜想1时求的8点分解数，我们发现，由再次符合了我们的想法。
在实际编码的时候，或许我们这样就会直接用这个猜想去搏一搏了。
但是，我现在是在写博客2333，还是老实证明一下吧</p> <p>老实说，至此，我第一次想的时候没有想出如何证明：
后来想的证明，也比这篇博客写的复杂
参考博客：<code>https://blog.csdn.net/zhang20072844/article/details/17033931</code>
所以此处，我想引用这篇博客的证明：</p> <div class="language-txt line-numbers-mode"><pre class="language-text"><code>证明:

证明的要点是考虑划分中是否有1。

记:
A(n) = n的所有划分组成的集合，
B(n) = n的所有含有1的划分组成的集合，
C(n) = n的所有不含1的划分组成的集合，
则有: A(n) = B(n)∪C(n)。

又记:
f(n) = A(n)中元素的个数，
g(n) = B(n)中元素的个数，
h(n) = C(n)中元素的个数，
易知: f(n) = g(n) + h(n)。

我们先来证明: f(2m + 1) = f(2m)，
首先，2m + 1 的每个划分中至少有一个1，去掉这个1，就得到 2m 的一个划分，故 f(2m + 1)≤f(2m)。
其次，2m 的每个划分加上个1，就构成了 2m + 1 的一个划分，故 f(2m)≤f(2m + 1)。
综上，f(2m + 1) = f(2m)。

接着我们要证明: f(2m) = f(2m - 1) + f(m)，
把 B(2m) 中的划分中的1去掉一个，就得到 A(2m - 1) 中的一个划分，故 g(2m)≤f(2m - 1)。
把 A(2m - 1) 中的划分加上一个1，就得到 B(2m) 中的一个划分，故 f(2m - 1)≤g(2m)。
综上，g(2m) = f(2m - 1)。

把 C(2m) 中的划分的元素都除以2，就得到 A(m) 中的一个划分，故 h(2m)≤f(m)。
把 A(m) 中的划分的元素都乘2，就得到 C(2m) 中的一个划分，故 f(m)≤h(2m)。
综上，h(2m) = f(m)。

所以: f(2m) = g(2m) + h(2m) = f(2m - 1) + f(m)。                                            

这就证明了我们的递推公式。
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br><span class="line-number">17</span><br><span class="line-number">18</span><br><span class="line-number">19</span><br><span class="line-number">20</span><br><span class="line-number">21</span><br><span class="line-number">22</span><br><span class="line-number">23</span><br><span class="line-number">24</span><br><span class="line-number">25</span><br><span class="line-number">26</span><br><span class="line-number">27</span><br><span class="line-number">28</span><br><span class="line-number">29</span><br><span class="line-number">30</span><br><span class="line-number">31</span><br><span class="line-number">32</span><br><span class="line-number">33</span><br></div></div><p>Tips:个人的一些感受</p> <div class="language-txt line-numbers-mode"><pre class="language-text"><code>1）从找规律这一方面，或许能够解释说明，为什么我上次进行企业笔试的时候，会有找规律的题目
那是为了练习我们对于数字的敏感程度，比如碰到这样的题目，我们可以猜想出猜想1）和2）这两种。
但是，一般的，要是不锻炼，或许，我们就只会做出猜想1）就以为只有这种规律了，但是其实，猜想2）页可以解释，而且才是最正确的。
2）此外，也解释了，为什么，我们在做笔试的题目发现有的题目可能有2种及以上的猜想都似乎可以
那样，只是说明，你的数字敏感度和思维广度很不同，但是，遗憾的，有时候碰到那样，没有后续数据给你验证，
你可能就陷入了2个选项啥的纠结，这种情况，我碰到了几次，，，（个人觉得，那是笔试这种题目的缺陷之处，或许改为，先选，然后把思路写下来，提交，按照思路进行判卷，比单纯的选择题更好）
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br></div></div><h4 id="_3）代码"><a href="#_3）代码" class="header-anchor">#</a> 3）代码</h4> <h5 id="写法1——递归"><a href="#写法1——递归" class="header-anchor">#</a> 写法1——递归</h5> <p>优点：简洁
缺点：数据大的时候，会由于调用栈太深，有问题</p> <div class="language-cpp line-numbers-mode"><pre class="language-cpp"><code><span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span><span class="token string">&lt;stdio.h&gt;</span></span>

<span class="token keyword">int</span> <span class="token function">solution</span><span class="token punctuation">(</span><span class="token keyword">int</span> n<span class="token punctuation">)</span>
<span class="token punctuation">{</span>
	<span class="token keyword">if</span><span class="token punctuation">(</span><span class="token number">1</span><span class="token operator">==</span>n<span class="token punctuation">)</span>
	<span class="token punctuation">{</span>
		<span class="token keyword">return</span> <span class="token number">1</span><span class="token punctuation">;</span>
	<span class="token punctuation">}</span>
	<span class="token keyword">else</span> <span class="token keyword">if</span><span class="token punctuation">(</span>n<span class="token operator">&amp;</span><span class="token number">1</span><span class="token punctuation">)</span><span class="token comment">//奇数 </span>
	<span class="token punctuation">{</span>
		<span class="token keyword">return</span> <span class="token function">solution</span><span class="token punctuation">(</span>n<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
	<span class="token punctuation">}</span>
	<span class="token keyword">else</span>
	<span class="token punctuation">{</span>
		<span class="token keyword">return</span> <span class="token function">solution</span><span class="token punctuation">(</span>n<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">)</span><span class="token operator">+</span><span class="token function">solution</span><span class="token punctuation">(</span>n<span class="token operator">/</span><span class="token number">2</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
	<span class="token punctuation">}</span> 
<span class="token punctuation">}</span>


<span class="token keyword">int</span> <span class="token function">main</span><span class="token punctuation">(</span><span class="token punctuation">)</span>
<span class="token punctuation">{</span>
	<span class="token keyword">int</span> n<span class="token punctuation">;</span>
	<span class="token keyword">while</span><span class="token punctuation">(</span><span class="token operator">~</span><span class="token function">scanf</span><span class="token punctuation">(</span><span class="token string">&quot;%d&quot;</span><span class="token punctuation">,</span><span class="token operator">&amp;</span>n<span class="token punctuation">)</span><span class="token punctuation">)</span>
	<span class="token punctuation">{</span>
		<span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">&quot;%d\n&quot;</span><span class="token punctuation">,</span><span class="token function">solution</span><span class="token punctuation">(</span>n<span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
	<span class="token punctuation">}</span>
	
	<span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br><span class="line-number">17</span><br><span class="line-number">18</span><br><span class="line-number">19</span><br><span class="line-number">20</span><br><span class="line-number">21</span><br><span class="line-number">22</span><br><span class="line-number">23</span><br><span class="line-number">24</span><br><span class="line-number">25</span><br><span class="line-number">26</span><br><span class="line-number">27</span><br><span class="line-number">28</span><br><span class="line-number">29</span><br></div></div><h5 id="写法2—打表技巧"><a href="#写法2—打表技巧" class="header-anchor">#</a> 写法2—打表技巧</h5> <div class="language-cpp line-numbers-mode"><pre class="language-cpp"><code><span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span><span class="token string">&lt;cstdio&gt;</span></span>
<span class="token keyword">const</span> <span class="token keyword">int</span> maxn<span class="token operator">=</span><span class="token number">100000</span><span class="token operator">+</span><span class="token number">5</span><span class="token punctuation">;</span>
<span class="token keyword">int</span> solution<span class="token punctuation">[</span>maxn<span class="token punctuation">]</span><span class="token operator">=</span><span class="token punctuation">{</span><span class="token number">0</span><span class="token punctuation">}</span><span class="token punctuation">;</span>

<span class="token keyword">void</span> <span class="token function">init</span><span class="token punctuation">(</span><span class="token punctuation">)</span>
<span class="token punctuation">{</span>
	solution<span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token operator">=</span><span class="token number">1</span><span class="token punctuation">;</span>
	solution<span class="token punctuation">[</span><span class="token number">2</span><span class="token punctuation">]</span><span class="token operator">=</span><span class="token number">2</span><span class="token punctuation">;</span>
	solution<span class="token punctuation">[</span><span class="token number">3</span><span class="token punctuation">]</span><span class="token operator">=</span><span class="token number">2</span><span class="token punctuation">;</span>
	<span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i<span class="token operator">=</span><span class="token number">4</span><span class="token punctuation">;</span>i<span class="token operator">&lt;</span>maxn<span class="token punctuation">;</span><span class="token operator">++</span>i<span class="token punctuation">)</span>
	<span class="token punctuation">{</span>
		<span class="token keyword">if</span><span class="token punctuation">(</span>i<span class="token operator">&amp;</span><span class="token number">1</span><span class="token punctuation">)</span> 
		<span class="token punctuation">{</span>
			solution<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token operator">=</span>solution<span class="token punctuation">[</span>i<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">;</span>
		<span class="token punctuation">}</span>
		<span class="token keyword">else</span>
		<span class="token punctuation">{</span>
			solution<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token operator">=</span>solution<span class="token punctuation">[</span>i<span class="token operator">/</span><span class="token number">2</span><span class="token punctuation">]</span><span class="token operator">+</span>solution<span class="token punctuation">[</span>i<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">;</span>
		<span class="token punctuation">}</span>
	<span class="token punctuation">}</span> 
<span class="token punctuation">}</span>

<span class="token keyword">int</span> <span class="token function">main</span><span class="token punctuation">(</span><span class="token punctuation">)</span>
<span class="token punctuation">{</span>
	<span class="token function">init</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span><span class="token comment">//讲所有的弄出来 </span>
	<span class="token keyword">int</span> n<span class="token punctuation">;</span>
	<span class="token keyword">while</span><span class="token punctuation">(</span><span class="token operator">~</span><span class="token function">scanf</span><span class="token punctuation">(</span><span class="token string">&quot;%d&quot;</span><span class="token punctuation">,</span><span class="token operator">&amp;</span>n<span class="token punctuation">)</span><span class="token punctuation">)</span>
	<span class="token punctuation">{</span>
		<span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">&quot;%d\n&quot;</span><span class="token punctuation">,</span>solution<span class="token punctuation">[</span>n<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
	<span class="token punctuation">}</span>
	
	<span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>

</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br><span class="line-number">17</span><br><span class="line-number">18</span><br><span class="line-number">19</span><br><span class="line-number">20</span><br><span class="line-number">21</span><br><span class="line-number">22</span><br><span class="line-number">23</span><br><span class="line-number">24</span><br><span class="line-number">25</span><br><span class="line-number">26</span><br><span class="line-number">27</span><br><span class="line-number">28</span><br><span class="line-number">29</span><br><span class="line-number">30</span><br><span class="line-number">31</span><br><span class="line-number">32</span><br><span class="line-number">33</span><br><span class="line-number">34</span><br></div></div><p>最后：</p> <ul><li>还有一篇文章讲解了用DP和DFS剪枝来做这题，非常棒</li> <li>链接：<code>https://www.jianshu.com/p/216b692d32ea</code></li> <li>还有，发现自己的不足，进行补充知识点——分区（数论）-维基百科</li></ul> <h2 id="_02-dp基础⭐️"><a href="#_02-dp基础⭐️" class="header-anchor">#</a> 02.dp基础⭐️</h2> <h3 id="_2-1-适用情况"><a href="#_2-1-适用情况" class="header-anchor">#</a> 2.1.适用情况</h3> <blockquote><p>维基百科：</p></blockquote> <ul><li>1）<strong>最优子结构性质</strong>。如果问题的最优解所包含的子问题的解也是最优的，我们就称该问题具有最优子结构性质（即满足最优化原理）。最优子结构性质为动态规划算法解决问题提供了重要线索。</li> <li>2）<strong>无后效性</strong>。即子问题的解一旦确定，就不再改变，不受在这之后、包含它的更大的问题的求解决策影响。</li> <li>3）<strong>子问题重叠性质</strong>。子问题重叠性质是指在用递归算法自顶向下对问题进行求解时，每次产生的子问题并不总是新问题，有些子问题会被重复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只计算一次，然后将其计算结果保存在一个表格中，当再次需要计算已经计算过的子问题时，只是在表格中简单地查看一下结果，从而获得较高的效率，降低了时间复杂度。</li></ul> <h3 id="_2-2-动态规划解题的『一般思路』"><a href="#_2-2-动态规划解题的『一般思路』" class="header-anchor">#</a> 2.2.动态规划解题的『一般思路』</h3> <ul><li>可以参考这篇<a href="https://www.zhihu.com/question/23995189" target="_blank" rel="noopener noreferrer">知乎<svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg></a></li> <li>还可以参考北大郭炜的两种『递推』的写法：“人人为我”和“为为人人”</li></ul> <h3 id="_2-3-动态规划思考和答疑"><a href="#_2-3-动态规划思考和答疑" class="header-anchor">#</a> 2.3.动态规划思考和答疑</h3> <blockquote><p>（1）动态规划的实现方式</p></blockquote> <ul><li>Q：动态规划只能用『递推』写嘛？</li> <li>A：不是的，动态规划可以用『递归』和『递推』这2种都可以，动态规划只是一个思考方式</li></ul> <blockquote><p>（2）动态规划的常见写法有</p></blockquote> <ul><li>Q：动态规划的常见写法？</li> <li>A：比如下面5种方式
<ul><li>递归</li> <li>递归改为栈来模拟</li> <li>递推</li> <li>递推+数组来辅助加速『<strong>备忘录</strong>写法』</li> <li>递推+更少的数组辅助『<strong>滚动数组</strong>”优化』</li></ul></li></ul> <p>其实动态规划将大事化下，小事化了的想法和“分治法”很像。</p> <h4 id="_2-3-1动态规划中的系列概念"><a href="#_2-3-1动态规划中的系列概念" class="header-anchor">#</a> 2.3.1动态规划中的系列概念</h4> <p><strong>深刻理解下面两句话：</strong>
动态规划是一种解决问题的方法：多阶段“决策”。
动态规划是一种思想：大问题转换为小问题。</p> <p>1）“<strong>备忘录</strong>写法”——其实就是将已经计划出来的数据保留下来，避免重复计算，可以说就是“<strong>打表技巧</strong>”
2）“<strong>滚动数组</strong>”优化——这是，其实是将状态转移的时候，需要借助的数据尽可能的减少，因为一般转移的时候，只需要临近的几个数据，并不需要全部的，“滚动数组”是一种减少空间复杂度的手段。
3）阶段和状态
4）DAG（有向无环图）
5）线性规划是一次性就</p> <h4 id="_2-3-2-两种动态规划的解题思路（极客时间）"><a href="#_2-3-2-两种动态规划的解题思路（极客时间）" class="header-anchor">#</a> 2.3.2.两种动态规划的解题思路（极客时间）</h4> <p>它们分别是状态转移表法和状态转移方程法。</p> <p>其中，状态转移表法解题思路大致可以概括为，回溯算法实现 - 定义状态 - 画递归树 - 找重复子问题 画状态转移表 - 根据递推关系填表 - 将填表过程翻译成代码。</p> <p>状态转移方程法的大致思路可以概括为，找最优子结构 - 写状态转移方程 - 将状态转移方程翻译成代码</p> <blockquote><p>九章算法</p></blockquote> <ul><li>什么情况下使用动态规划？
<ul><li>满足下面三个条件之一, 则极有可能是使用动态规划求解
<ul><li>求最大值最小值</li> <li>判断是否可行</li> <li>统计方案个数</li></ul></li></ul></li></ul> <h2 id="_03-dp的启发性思维导图"><a href="#_03-dp的启发性思维导图" class="header-anchor">#</a> 03.DP的启发性思维导图</h2> <ul><li>1、<strong>BFS本身就是一种DP</strong></li> <li>2、DP的2种写法：递归和递推（又叫迭代）</li></ul> <h2 id="🍁参考资料"><a href="#🍁参考资料" class="header-anchor">#</a> 🍁参考资料</h2> <ul><li><a href="https://github.com/tianyicui/pack" target="_blank" rel="noopener noreferrer">背包九讲<svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg></a>-<code>Tianyi Cui</code></li> <li>算法笔记-胡凡</li> <li><a href="https://www.bilibili.com/video/BV1bb411t7FK" target="_blank" rel="noopener noreferrer">从运筹学的数学角度讲“动态规划”<svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg></a></li> <li>极客时间-数据结构与算法之美-王争</li> <li><a href="https://oi-wiki.org/" target="_blank" rel="noopener noreferrer">OI.wiki<svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg></a></li> <li><a href="https://github.com/ChenBohan/Algorithm-JiuZhang-Basic-03-Dynamic-Programming" target="_blank" rel="noopener noreferrer">九章算法<svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg></a>，GitHub</li></ul></div> <div class="page-edit"><!----> <!----></div> <!----> </div> <!----></div></div>
    <script src="/assets/js/app.c70e21ad.js" defer></script><script src="/assets/js/63.6f8a4742.js" defer></script>
  </body>
</html>
